/*
 * 栈 (Stack) - C#实现
 * C#提供内置Stack<T>，LIFO，所有操作O(1)
 */

using System;
using System.Collections.Generic;

namespace DataStructures
{
    public class MyStack<T>
    {
        private List<T> _items = new List<T>();

        public void Push(T item) => _items.Add(item);
        
        public T Pop()
        {
            if (IsEmpty) throw new InvalidOperationException("栈为空");
            T item = _items[_items.Count - 1];
            _items.RemoveAt(_items.Count - 1);
            return item;
        }
        
        public T Peek()
        {
            if (IsEmpty) throw new InvalidOperationException("栈为空");
            return _items[_items.Count - 1];
        }
        
        public bool IsEmpty => _items.Count == 0;
        public int Count => _items.Count;
    }

    public class StackExamples
    {
        // 括号匹配
        public static bool CheckBrackets(string expression)
        {
            var stack = new Stack<char>();
            var pairs = new Dictionary<char, char> 
            { 
                {'(', ')'}, {'[', ']'}, {'{', '}'} 
            };

            foreach (char ch in expression)
            {
                if (pairs.ContainsKey(ch))
                    stack.Push(ch);
                else if (pairs.ContainsValue(ch))
                {
                    if (stack.Count == 0 || pairs[stack.Pop()] != ch)
                        return false;
                }
            }
            return stack.Count == 0;
        }
    }

    public class StackProgram
    {
        public static void Main()
        {
            Console.WriteLine("╔════════════════════════════════════════╗");
            Console.WriteLine("║   栈 (Stack) - C#实现                  ║");
            Console.WriteLine("╚════════════════════════════════════════╝");

            var stack = new MyStack<int>();
            stack.Push(10);
            stack.Push(20);
            stack.Push(30);
            Console.WriteLine($"\n弹出: {stack.Pop()}");
            Console.WriteLine($"栈顶: {stack.Peek()}");

            Console.WriteLine("\n--- 括号匹配 ---");
            string[] tests = { "{[()]}", "{[(])}" };
            foreach (var test in tests)
            {
                bool match = StackExamples.CheckBrackets(test);
                Console.WriteLine($"  {test} → {(match ? "匹配✓" : "不匹配✗")}");
            }

            Console.WriteLine("\n✅ 优势: 所有操作O(1)，LIFO适合很多场景");
            Console.WriteLine("⚠️ 局限: 只能访问栈顶");
            Console.WriteLine("💡 应用: 括号匹配、函数调用、浏览器后退");
        }
    }
}
